package cxydmmszl.chapter01.t008;

import java.util.*;

/**
 * <li style="color: red;">Prob</li>
 * 单调栈结构
 * <li style="color: red;">Desc</li>
 * 给定一个不含重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。
 * 返回所有位置相应的信息。
 * <li style="color: red;">Link</li> CD101
 *
 * @author habitplus
 * @since 2021-08-26 09:51
 */
public class Main {
    public int[][] rightWay01(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        int n = arr.length;
        int[][] ans = new int[n][2];
        int[] aux = new int[n];
        int j;

        for (int i = n - 1; i >= 0; i--) {
            aux[i] = -1;
            j = i + 1;
            while (j < n && j != -1) {
                if (arr[i] > arr[j]) {
                    aux[i] = j;
                    break;
                } else {
                    j = aux[j];
                }
            }
        }

//        System.out.println(Arrays.toString(aux));

        for (int i = 0; i < n; i++) {
            ans[i][1] = aux[i];
            aux[i] = -1;
            j = i - 1;
            while (j >= 0) {
                if (arr[i] > arr[j]) {
                    aux[i] = j;
                    break;
                } else {
                    j = aux[j];
                }
            }

            ans[i][0] = aux[i];
        }

//        System.out.println(Arrays.toString(aux));

        return ans;
    }

    public int[][] rightWay02(int[] arr) {
        /*
         * 解题思路：单调栈（数组不含重复的数）
         *      准备一个栈 stack，栈中存放数组的位置下标；
         *      如果找到每一个位置左边和右边离 i 位置最近且值比 arr[i] 小的位置，
         *      那么需要让 stack 从栈顶到栈底的位置所代表的值是严格递减的
         */
        if (arr == null || arr.length == 0) {
            return null;
        }

        int n = arr.length;
        int[][] ans = new int[n][2];
        Stack<Integer> stack = new Stack<>();
        int j;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                j = stack.pop();
                ans[j][0] = stack.isEmpty() ? -1 : stack.peek();
                ans[j][1] = i;
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            j = stack.pop();
            ans[j][0] = stack.isEmpty() ? -1 : stack.peek();
            ans[j][1] = -1;
        }

        return ans;
    }

    public int[][] rightWay03(int[] arr) {
        /*
         * 解题思路：单调栈（数组含重复的数）
         *      准备一个栈 stack，栈中存放数组的位置下标；
         *      如果找到每一个位置左边和右边离 i 位置最近且值比 arr[i] 小的位置，
         *      那么需要让 stack 从栈顶到栈底的位置所代表的值是严格递减的
         */
        if (arr == null || arr.length < 1) {
            return null;
        }

        int n = arr.length;
        int[][] ans = new int[n][2];

        // 声明一个从栈顶到栈底递减的栈，相同的数直接合并
        Stack<List<Integer>> monotonyStack = new Stack<>();

        List<Integer> tmpList;

        for (int i = 0; i < n; i++) {
            // 栈顶所代表的位置的值比 arr[i] 大，则出栈
            while (!monotonyStack.isEmpty() && arr[monotonyStack.peek().get(0)] > arr[i]) {
                tmpList = monotonyStack.pop();
                // 如果左边最近且比 popList 所代表的值小的位置存在（stack 不为空），取最晚进栈的位置
                int leftLessIdx = monotonyStack.isEmpty() ?
                        -1 : monotonyStack.peek().get(monotonyStack.peek().size() - 1);

                for (int e : tmpList) {
                    ans[e][0] = leftLessIdx;
                    ans[e][1] = i;
                }
            }

            // 栈顶所代表的位置的值 与 arr[i] 相等，则直接加入到栈顶列表；否则，需要新建列表，再进栈
            if (!monotonyStack.isEmpty() && arr[monotonyStack.peek().get(0)] == arr[i]) {
                monotonyStack.peek().add(i);
            } else {
                tmpList = new ArrayList<>();
                tmpList.add(i);
                monotonyStack.push(tmpList);
            }
        }

        while (!monotonyStack.isEmpty()) {
            tmpList = monotonyStack.pop();
            // 如果左边最近且比 popList 所代表的值小的位置存在（stack 不为空），取最晚进栈的位置
            int leftLessIdx = monotonyStack.isEmpty() ?
                    -1 : monotonyStack.peek().get(monotonyStack.peek().size() - 1);

            for (int e : tmpList) {
                ans[e][0] = leftLessIdx;
                ans[e][1] = -1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
//        System.out.println(Arrays.deepToString(new Main().rightWay03(new int[]{3, 4, 1, 5, 6, 2, 7})));
        System.out.println(Arrays.deepToString(new Main().rightWay03(new int[]{3, 1, 3, 4, 3, 5, 3, 2, 2})));
        System.out.println(Arrays.deepToString(new Main().rightWay03(new int[]{3, 1, 3, 4, 3, 5, 3, 2, 2, 1})));
    }

//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] arr = new int[n];
//        for (int i = 0; i < n; i++) {
//            arr[i] = sc.nextInt();
//        }
//
//        Main test = new Main();
//        int[][] ans = test.rightWay01(arr);
//
//        StringBuilder sb = new StringBuilder();
//        for (int[] a : ans) {
//            sb.append(a[0]).append(" ").append(a[1]).append("\n");
//        }
//        System.out.println(sb.toString());
//    }
}
